/**
  @(#)$Id: AL_QueuePriorityList.h 74 2013-10-10 12:42:07Z xiaoting $
  @brief   
  ////////////////////////////////Priority queue (priority queue)e//////////////////////////////////////////
  Common queue is a FIFO data structure, the end of an additional element in the queue, and the head removed from the queue. In the 
  priority queue element is given priority. When accessing the element, the element with the highest priority first removed. Priority 
  queue with the highest first-out (largest-in, first-out) the behavioral characteristics.
  
  Priority queue is 0 or more elements of the collection, each element has a priority or value of the operations performed on the 
  priority queue with a) Find; 2) Insert a new element; 3) Delete in the minimum priority queue (min priorityq ueue), the lookup 
  operation to search for smallest element priority, delete operation to remove the element; for maximum priority queue (max priority 
  queue), lookup to search for the largest element of the priority, delete operation is used remove the element. priority queue 
  element can have the same priority, find and delete operations can be carried out according to any priority.

  A queue is a special linear form, so special is that it only allows the front end of the table (front) delete operation, 
  and the rear end of the table (rear) for insertion, and the stack, as the queue is an operating by restricted linear form. Insert 
  operation is called the tail end, the end delete operation called HOL. No element in the queue, it is called an empty queue.
  
  This data structure in the queue, the first element inserted will be the first element to be removed; otherwise the last inserted 
  element will be the last element to be removed, so the queue is also known as "first in first out" (FIFO-first in first out) linear 
  form.

  @Author $Author: xiaoting $
  @Date $Date: 2013-10-10 20:42:07 +0800 (周四, 10 十月 2013) $
  @Revision $Revision: 74 $
  @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_QueuePriorityList.h $
  @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_QueuePriorityList.h 74 2013-10-10 12:42:07Z xiaoting $
 */

#ifndef CXX_AL_QUEUEPRIORITYLIST_H
#define CXX_AL_QUEUEPRIORITYLIST_H

#ifndef CXX_AL_NODE_H
#include "AL_Node.h"
#endif

///////////////////////////////////////////////////////////////////////////
//			AL_QueuePriorityList
///////////////////////////////////////////////////////////////////////////

template<typename T, typename Compare = al_less<T> > 
class AL_QueuePriorityList
{
public:
	/**
	* Construction Constructed using the default priority queue
	*
	* @param
	* @return
	* @note
	* @attention	The default precedence relations: big > small
	*/
	AL_QueuePriorityList();

	/**
	* Destruction
	*
	* @param
	* @return
	* @note
	* @attention
	*/
	~AL_QueuePriorityList();

	/**
	* IsEmpty
	*
	* @param	VOID
	* @return	BOOL
	* @note		Returns true queue is empty
	* @attention
	*/
	BOOL IsEmpty() const;

	/**
	* Front
	*
	* @param	T& tTypeOut <OUT>
	* @return	BOOL
	* @note		Returns a reference to the first element at the front of the queue.
	* @attention
	*/
	BOOL Front(T& tTypeOut) const;

	/**
	* Back
	*
	* @param	T& tTypeOut <OUT>
	* @return	BOOL
	* @note		Returns a reference to the last and most recently added element at the back of the queue.
	* @attention
	*/
	BOOL Back(T& tTypeOut) const;

	/**
	* Pop
	*
	* @param	T& tTypeOut <OUT>
	* @return	BOOL
	* @note		Removes an element from the front of the queue.
	* @attention
	*/
	BOOL Pop(T& tTypeOut);

		
	/**
	* Push
	*
	* @param	const T& tData
	* @return	BOOL
	* @note		Adds an element to the back of the queue.
	* @attention	
	*/
	BOOL Push(const T& tData);

	/**
	* Size
	*
	* @param	VOID
	* @return	DWORD
	* @note		Returns the number of elements in the queue
	* @attention
	*/
	DWORD Size() const;

	/**
	* Clear
	*
	* @param	VOID
	* @return	VOID
	* @note		clear all data
	* @attention
	*/
	VOID Clear();
	
protected:
private:
	/**
	*Copy Construct
	*
	* @param const AL_QueuePriorityList<T, Compare>& cAL_QueuePriorityList
	* @return
	*/
	AL_QueuePriorityList(const AL_QueuePriorityList<T, Compare>& cAL_QueuePriorityList);

	/**
	*Assignment
	*
	* @param const AL_QueuePriorityList<T, Compare>& cAL_QueuePriorityList
	* @return AL_QueuePriorityList<T, Compare>&
	*/
	AL_QueuePriorityList<T, Compare>& operator = (const AL_QueuePriorityList<T, Compare>& cAL_QueuePriorityList);

public:
protected:
private: 
	AL_Node<T>*		m_pHeader;
	DWORD			m_dwSize;

	AL_Node<T>*		m_pFront;
	AL_Node<T>*		m_pRear;
};


/**
* Construction Constructed using the default priority queue
*
* @param
* @return
* @note
* @attention	The default precedence relations: big > small
*/
template<typename T, typename Compare> 
AL_QueuePriorityList<T, Compare>::AL_QueuePriorityList():
m_pHeader(NULL),
m_dwSize(0x00),
m_pFront(NULL),
m_pRear(NULL)
{
	m_pHeader = new AL_Node<T>;
}

/**
* Destruction
*
* @param
* @return
* @note
* @attention
*/
template<typename T, typename Compare> 
AL_QueuePriorityList<T, Compare>::~AL_QueuePriorityList()
{
	Clear();
	//delete the header
	if (NULL != m_pHeader) {
		delete m_pHeader;
		m_pHeader = NULL;
	}
}

/**
* IsEmpty
*
* @param	VOID
* @return	BOOL
* @note		Returns true queue is empty
* @attention
*/
template<typename T, typename Compare> BOOL 
AL_QueuePriorityList<T, Compare>::IsEmpty() const
{
	return (0x00 == m_pHeader->m_pNext) ? TRUE:FALSE;
}


/**
* Front
*
* @param	T& tTypeOut <OUT>
* @return	BOOL
* @note		Returns a reference to the first element at the front of the queue.
* @attention
*/
template<typename T, typename Compare> BOOL 
AL_QueuePriorityList<T, Compare>::Front(T& tTypeOut) const
{
	if (TRUE ==IsEmpty()) {
		return FALSE;
	}

	tTypeOut = m_pFront->m_tData;
	return TRUE;
}

/**
* Back
*
* @param	T& tTypeOut <OUT>
* @return	BOOL
* @note		Returns a reference to the last and most recently added element at the back of the queue.
* @attention
*/
template<typename T, typename Compare> BOOL 
AL_QueuePriorityList<T, Compare>::Back(T& tTypeOut) const
{
	if (TRUE ==IsEmpty()) {
		return FALSE;
	}

	tTypeOut = m_pRear->m_tData;
	return TRUE;
}

/**
* Pop
*
* @param	T& tTypeOut <OUT>
* @return	BOOL
* @note		Removes an element from the front of the queue.
* @attention
*/
template<typename T, typename Compare> BOOL 
AL_QueuePriorityList<T, Compare>::Pop(T& tTypeOut)
{
	if (TRUE ==IsEmpty()) {
		return FALSE;
	}
	
	AL_Node<T>*	pPop = m_pFront;
	//get the previous node of m_pRear
	m_pHeader->m_pNext = pPop->m_pNext;
	if (m_pRear != pPop) {
		pPop->m_pNext->m_pPre = m_pHeader;
	}
	else {
		//pop is the rear
		m_pRear = NULL;
	}
	m_pFront = pPop->m_pNext;

	tTypeOut = pPop->m_tData;

	//delete the top
	delete pPop;
	pPop = NULL;

	m_dwSize--;
	return TRUE;
}

	
/**
* Push
*
* @param	const T& tData
* @return	BOOL
* @note		Adds an element to the back of the queue.
* @attention	
*/
template<typename T, typename Compare> BOOL 
AL_QueuePriorityList<T, Compare>::Push(const T& tData)
{
	AL_Node<T>*	pPush = new AL_Node<T>;
	if (NULL == pPush) {
		//new error
		return FALSE;
	}
	pPush->m_tData = tData;

	if (TRUE == IsEmpty()) {
		//the first time Push, not need to ++
		pPush->m_pPre = m_pHeader;
		pPush->m_pNext = NULL;
		m_pHeader->m_pNext = pPush;
		m_pFront = pPush;
		m_pRear = pPush;
	}	
	else {
		AL_Node<T>*	pMove = m_pRear;
		AL_Node<T>*	pMovePre = m_pFront;
		while(m_pHeader != pMove) {
			//loop all elements: from the back
			if (FALSE == Compare()(tData, pMove->m_tData)) {
				break;
			}
			pMove = pMove->m_pPre;
		}

		pPush->m_pPre = pMove;
		pPush->m_pNext = pMove->m_pNext;
		if (NULL != pMove->m_pNext) {
			pMove->m_pNext->m_pPre = pPush;
		}
		pMove->m_pNext = pPush;

		if (m_pHeader == pMove) {
			//Compare all elements in the queue (insert to the front)
			//inset to the front		
			m_pFront = pPush;
		}
		else if (m_pRear == pMove) {
			//inset to the m_pRear
			m_pRear = pPush;
		}
		else {
			//no thing to do
		}
	}

	m_dwSize++;
	return TRUE;
}

/**
* Size
*
* @param	VOID
* @return	DWORD
* @note		Returns the number of elements in the queue
* @attention
*/
template<typename T, typename Compare> DWORD 
AL_QueuePriorityList<T, Compare>::Size() const
{
	return m_dwSize;
}

/**
* Clear
*
* @param	VOID
* @return	VOID
* @note		clear all data
* @attention
*/
template<typename T, typename Compare> VOID 
AL_QueuePriorityList<T, Compare>::Clear()
{
	AL_Node<T>* pDelete = NULL;
	while(NULL != m_pHeader->m_pNext){
		//get the node
		pDelete = m_pHeader->m_pNext;
		m_pHeader->m_pNext = pDelete->m_pNext;
		delete pDelete;
		pDelete = NULL;
	}
	m_dwSize = 0x00;
}

#endif // CXX_AL_QUEUEPRIORITYLIST_H
/* EOF */
